﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0094_FindNumberOfLIS : IAlgorithm
    {
        // 673. 最长递增子序列的个数

        // 给定一个未排序的整数数组，找到最长递增子序列的个数。

        // 注意: 给定的数组长度不超过 2000 并且结果一定是32位有符号整数。

        public void Test()
        {
            // 算法参数定义

            // 算法执行与打印
            //Console.WriteLine(Algorithm());
            //var res = Algorithm(param);
            //foreach (var item in res)
            //{
            //    foreach (var iitem in item)
            //    {
            //        Console.Write(iitem + " ");
            //    }
            //    Console.WriteLine();
            //}
        }

        // 算法
        public int FindNumberOfLIS(int[] nums)
        {
            int n = nums.Length, maxLen = 0, ans = 0;
            int[] dp = new int[n];
            int[] cnt = new int[n];
            for (int i = 0; i < n; ++i)
            {
                dp[i] = 1;
                cnt[i] = 1;
                for (int j = 0; j < i; ++j)
                    if (nums[i] > nums[j])
                        if (dp[j] + 1 > dp[i])
                        {
                            dp[i] = dp[j] + 1;
                            cnt[i] = cnt[j]; // 重置计数
                        }
                        else if (dp[j] + 1 == dp[i])
                        {
                            cnt[i] += cnt[j];
                        }
                if (dp[i] > maxLen)
                {
                    maxLen = dp[i];
                    ans = cnt[i]; // 重置计数
                }
                else if (dp[i] == maxLen)
                {
                    ans += cnt[i];
                }
            }
            return ans;
        }
    }
}
